package LeetCode.leetcode79;

class Solution {
    public static void main(String[] args) {

        char[][] board = new char[][]{{'C','A','A'},{'A','A','A'},{'B','C','D'}};
        String work = "AAB";
        new Solution().exist(board, work);
    }
    boolean res = false;
    public boolean exist(char[][] board, String word) {
        if(word.isEmpty())
            return false;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                run(board,i,j,0,word,visited);
            }
        }
        return res;
    }
    public void run(char[][] board, int m, int n, int index, String word, boolean[][] visited) {
        if (index == word.length()-1 && board[m][n] == word.charAt(index)) {
            res = true;
            return;
        }
        if (board[m][n] != word.charAt(index)) return;
        visited[m][n] = true;
        //向上拓展
        if (m - 1 >= 0 && !visited[m-1][n]) {
            index++;
            visited[m-1][n] = true;
            run(board,m-1,n,index,word,visited);
            index--;
            visited[m-1][n] = false;
        }
        //向右拓展
        if (n + 1 < board[0].length && !visited[m][n + 1]) {
            index++;
            visited[m][n + 1] = true;
            run(board,m,n+1,index,word,visited);
            visited[m][n+1] = false;
            index--;
        }
        //乡下拓展
        if (m + 1 < board.length && !visited[m+1][n]) {
            index++;
            visited[m+1][n] = true;
            run(board,m+1,n,index,word,visited);
            visited[m+1][n] = false;
            index--;
        }
        //向左拓展
        if (n - 1 >= 0 && !visited[m][n - 1]) {
            index++;
            visited[m][n - 1] = true;
            run(board,m,n-1,index,word,visited);
            visited[m][n - 1] = false;
            index--;
        }
        visited[m][n] = false;
    }
}